package DataStrucures;

import java.util.ArrayList;
import java.util.Collections;

public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int[]arr={13,7,8,3,29,6,1};
        CreatHuffManTree(arr);


    }
    public static void CreatHuffManTree(int[] arr){
        ArrayList<HuffManTree> arrayList=new ArrayList<>();
        for (int value : arr) {
            arrayList.add(new HuffManTree(value));
        }

        while (arrayList.size()>1){
            Collections.sort(arrayList);
            HuffManTree left=arrayList.get(0);
            HuffManTree right=arrayList.get(1);
            HuffManTree Node=new HuffManTree(left.value+right.value);
            Node.left=left;
            Node.right=right;
            arrayList.remove(left);
            arrayList.remove(right);
            arrayList.add(Node);

        }
        arrayList.get(0).preOrder();

    }

}
//
class HuffManTree implements Comparable<HuffManTree>{
    int value;
    HuffManTree left;
    HuffManTree right;

    public HuffManTree(int value) {
        this.value = value;
    }
    public  void preOrder(){
        System.out.println(this);
        if(this.left!=null){
            this.left.preOrder();
        }
        if(this.right!=null){
            this.right.preOrder();
        }
    }

    @Override
    public String toString() {
        return "HuffManTree{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(HuffManTree o) {
        //实现从小到大排序
        return this.value-o.value;
    }
}
